467. 环绕字符串中唯一的子字符串

Similar Question

leading to the advanced question

Solution Tips

方案一: 直接法

超时了

/**
 * @param {string} s
 * @return {number}
 */
var findSubstringInWraproundString = function(s) {
    // 单字母子串肯定是全都有的
    // 如果是多字母的子串, 就从头开始判断是否在连续的 字母表中, 如果是就 count++
    const alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('');
    // const abortLenList = {};
    // let count = [...new Set(s.split(''))].length
    // for (let i = 0; i < s.length; i++) {
    //     let start = s[i];
    //     let subLen = 1;
    //     let lastCharIndex = alphabet.indexOf(s[i]);
    //     // 单字母的, 需要判断一下子串是否相同, 去重后计数即可
    //     for (let j = i + 1; j < s.length; j++) {
    //         // 直接从多字母子串开始处理即可
    //         const newCharIndex = alphabet.indexOf(s[j])
    //         if (newCharIndex !== -1 && newCharIndex === (lastCharIndex + 1) % 26) {
    //             // 连续的子串, 且是字母表的子串
    //             subLen++
    //             // 再判断一下长度是否重复即可
    //             if (subLen > (abortLenList[start] || 0)) {
    //                 count++;
    //                 // 子串有可能重复出现, 要记录每个字母最长的 len, 下一次直接从这里开始就行
    //                 abortLenList[start] = subLen
    //             }
    //             // 无论是否重复, 都要更新 last
    //             lastCharIndex = newCharIndex;
    //         }
    //         else {
    //             // 中断, 后面以 s[i] 开头的子串都不符合题意了
    //             break;
    //         }
    //     }
    // }

    // 参考上一题的思路, 不用每个子串遍历, 直接找到最长的子串, 然后那个子串就已经包含了所有的答案了
    // 寻找最长子串
    let longest = '';
    for (let i = 0; i < s.length; i++) {
        const start = s[i];
        const alphabetIndex = alphabet.indexOf(start);
        let nextChar = alphabet[(alphabetIndex+1) % 26]
        for (let j = i + 1; j < s.length; j++) {
            if (s[j] === nextChar) {

            }
        }
    }

    return count;
};

console.log(findSubstringInWraproundString('abaab'))

方案二: 动态规划

对于两个以同一个字符结尾的子串，长的那个子串必然包含短的那个

var findSubstringInWraproundString = function(p) {
    const dp = new Array(26).fill(0);
    let k = 0;
    for (let i = 0; i < p.length; ++i) {
        if (i > 0 && (p[i].charCodeAt() - p[i - 1].charCodeAt() + 26) % 26 === 1) { // 字符之差为 1 或 -25
            ++k;
        } else {
            k = 1;
        }
        dp[p[i].charCodeAt() - 'a'.charCodeAt()] = Math.max(dp[p[i].charCodeAt() - 'a'.charCodeAt()], k);
    }
    return _.sum(dp);
};